上一篇我們從超商結帳、客服電話與列印工作認識了 Queue。
簡單複習一下 Queue，例如四個人依序進入隊伍：

A → B → C → D

那麼處理順序自然就是：

A → B → C → D

這就是 FIFO（First In, First Out）先來先處理。
如果大家處理的事情差不多重要，這是一個非常合理的規則。
但如果今天我們把場景換成急診室呢？
同理心讓這個順序產生了複雜的變化。

急診室真的應該先到先服務嗎？

假設現在有四位病患：

A：輕微擦傷
B：胸痛、呼吸困難
C：輕微發燒
D：大量出血

他們抵達急診室的順序是：

A → B → C → D

如果完全按照 Queue 的 FIFO 規則：

先來 → 先處理

那麼 A 應該第一個接受治療，接著 B、C，最後才輪到 D。
但這顯然不是我們真正想要的結果，因為真正輪到 D 時，可能需要聯絡殯儀館了。

所以現在影響處理順序的是：

誰現在更需要被處理？

也就是說，我們原本描述問題的方式已經改變了。

Queue 沒有錯，是問題變了

我們現在面對的問題，已經不符合 Queue 原本想表達的語意。
上一篇我們的問題是誰先來？，所以 Queue 很適合。
但急診室考量的問題比較接近：

目前等待的人裡面，誰的優先程度最高？

這兩個問題的考量明顯不同，第一個問題關心的是到達順序，第二個問題關心的則是優先度。
既然「誰先被處理」的規則改變了，我們使用的資料結構自然也可能需要跟著改變。
這就是 Priority Queue（優先佇列） 想解決的問題。

Priority Queue：不是最早的先出來，而是最重要的先出來

普通 Queue 可以想像成：

A → B → C → D

先處理 A

Priority Queue 則會替每個項目附上一個 priority。
例如：

A(2)
B(5)
C(1)
D(4)

假設數字越大代表越重要，那麼我們真正想要的處理順序就是：

B(5)
D(4)
A(2)
C(1)

所以第一個被取出的不是最早加入的 A，而是 B(5)，因為 B 目前擁有最高的 priority。

priority 到底是什麼？

priority 並不是某種特殊的 JavaScript 型別。
它只是我們為資料定義的一個：

決定處理順序的依據

例如：

{
  patient: "A",
  priority: 2
}

或者：

{
  patient: "B",
  priority: 5
}

Priority Queue 不關心 B 是第幾個進來的，它只關心：

B 的 priority 是多少？

當然，真實世界的急診檢傷遠比單一數字複雜，這裡只是借用這個情境理解資料結構。
在其他系統裡，priority 也可能代表完全不同的事情。
例如作業排程：

工作 A：priority 2
工作 B：priority 10
工作 C：priority 4

或者伺服器中的任務：

一般背景工作：priority 1
使用者請求：priority 5
系統緊急工作：priority 10

甚至遊戲裡也可能有：

普通動畫：priority 1
角色輸入：priority 5
碰撞計算：priority 8

在中文與境裡，可能接近我們用的「權重」。

按照我們提供的 priority 大小，決定下一個應該取出誰。

其實我們真正需要的是「重複找最大值」

如果重新描述剛才的問題，我們會發現 Priority Queue 做的事情其實非常單純。
假設目前有：

A(2)
B(5)
C(1)
D(4)

第一次：

找最大的 priority
→ B(5)

把 B 處理掉之後：

A(2)
C(1)
D(4)

下一次再找最大的：

→ D(4)

剩下：

A(2)
C(1)

再找一次：

→ A(2)

所以這類問題可以被描述成：

Repeated Maximum Selection (反覆找出目前最大的元素)

如果規則相反，例如數字越小越重要，那麼問題則變成：

Repeated Minimum Selection (反覆找出目前最小的元素)

通常描述比較重要，因為當我們把問題從急診室要先處理誰？
轉換成：

我要反覆取得目前 priority 最大的元素

問題就開始變成一個可以用資料結構處理的模型。
這就是我們這個系列會重複做的事情：

現實問題
   ↓
找到真正影響決策的規則
   ↓
把規則變成資料之間的關係
   ↓
選擇適合的資料結構

那我每次把全部資料掃一遍不就好了？

當然可以，假設我們直接用 JavaScript Array：

const patients = [
  { name: "A", priority: 2 },
  { name: "B", priority: 5 },
  { name: "C", priority: 1 },
  { name: "D", priority: 4 },
];

要找 priority 最大的人，我們完全可以掃描整個 Array。
概念上就是：

A(2) ─┐
B(5)  │
C(1)  ├─ 全部看一次 → 找出 B(5)
D(4) ─┘

資料只有四筆的時候，這當然沒什麼問題。
但如果現在不是四筆，而是：

100 筆
1,000 筆
100,000 筆

而且我們不是只找一次，而是：

找最大值
移除它
再找最大值
再移除它
再找最大值
...

事情開始變得繁瑣了，我們只需要：

頻繁地加入新資料，並且反覆取出目前 priority 最高的資料

資料結構的選擇，就是從這種操作需求開始產生差異。

那每次排序呢？

另一個直覺做法是：

patients.sort((a, b) => b.priority - a.priority);

變成：

B(5)
D(4)
A(2)
C(1)

這樣第一個元素永遠就是 priority 最大的。
看起來問題解決了，但想像一下當 B 剛被處理完，突然又來了一位新的病患 E：

E(6)

然後我們加入：

D(4)
A(2)
C(1)
E(6)

為了重新維持完整排序，又要處理資料的位置。
接著又有人進來。
又有人離開。
又有人進來。
我們開始發現：

也許我們根本不需要知道所有人的完整排名。

我們真正需要知道的只有：

下一個是誰？

這是一個很重要的認知，完整排序在回答：

第一名是誰？
第二名是誰？
第三名是誰？
第四名是誰？
...

但 Priority Queue 最在意的是：

現在第一名是誰？

取走之後再問：

那現在第一名又是誰？

既然我們只需要維護這部分資訊，就不一定需要讓所有資料永遠保持完整排序。
這也帶出了 Priority Queue 最常見的實作方式之一：

Heap。

Heap：不用讓全部資料都有完整排名

Heap 是一種特殊的資料結構，這篇先不討論它完整的實作方式，只需要先理解它背後的想法。
假設我們建立的是一個 Max Heap，它會維持一個重要條件：

父節點的 priority 不小於它的子節點。

例如：

        5
      /   \
     4     1
    /
   2

你可能會注意到 4 > 2 但 2 > 1 卻沒有反映在位置上。這沒有關係，因為 Heap 根本不要求 5 > 4 > 2 > 1 全部要按照大小排好。

它只需要保證最大的元素在最上面，所以我們馬上知道：

下一個要處理的是 5

這正好符合 Priority Queue 的需求。

為什麼 Priority Queue 常用 Heap？

現在回頭看我們真正需要的操作：

加入一個新的項目

以及：

取出目前 priority 最高的項目

Heap 很適合這種模式，以常見的 Binary Heap 來說：

查看最高 priority
→ O(1)

加入新元素
→ O(log n)

取出最高 priority
→ O(log n)

這裡不用急著去背，只需要先注意一件事情：

Heap 不需要每次都重新把所有元素排好。

它只負責維持：

足以知道「下一個是誰」的結構

因此 Priority Queue 經常使用 Heap 來實作。
兩者的關係可以簡單理解成：

所以：

Priority Queue 是我們想要的操作語意，Heap 則是實現這種語意的一種常見資料結構。

這兩件事情並不是完全相同的概念。

Priority Queue 不一定只能處理「最大值」

剛才我們一直使用 priority 越大 → 越優先，這通常稱為 Max Priority Queue。
但也可以反過來定義 priority 越小 → 越優先，例如：

A(20)
B(5)
C(12)
D(2)

如果數字代表「預估剩餘時間」，我們可能希望先處理 D(2)。
這時真正需要的就是Repeated Minimum Selection，常見實作則可以使用Min Heap。

所以 Heap 通常可以分成兩種方向：

• Max Heap👉最大值在頂端
• Min Heap👉最小值在頂端

差別只在於：

你的問題認為「哪一種值」應該先被處理。

如果 priority 一樣呢？

通常馬上會有的疑問，假設：

A(5)
B(5)
C(3)

A 和 B 的 priority 一樣，那到底應該誰先？
這時我們就必須定義第二層規則，例如：

• priority 高的先處理
• priority 相同時，先來的先處理

於是我們可能實際比較的是：

第一條件：priority
第二條件：arrival order

這也提醒我們：

資料結構本身不會替我們決定什麼叫做「公平」或「重要」。

那些規則仍然來自問題本身，資料結構只是幫我們把規則表示出來。

從 Queue 到 Priority Queue，真正改變的是什麼？

如果只看 API，Queue 和 Priority Queue 好像沒有差很多。
可能都是：

queue.enqueue(value);
queue.dequeue();

Priority Queue 可能只是多了一個：

queue.enqueue(value, priority);

真正改變的是面對問題的考量：

Queue

問題規則：

誰先來？

所以：

最早進來的人
→ 最早被取出

Priority Queue

問題規則：

誰現在最重要？

所以：

priority 最高的人
→ 最早被取出

這也是為什麼我們不能只問：

「資料要放進 Array、Queue 還是 Heap？」

更重要的問題其實是：

「這些資料之間，到底存在什麼處理規則？」

當規則改變，適合的資料結構也會跟著改變。

回到最開始的急診室

現在重新看看兩種情況。

普通 Queue：

A → B → C → D

先處理 A

因為規則是先來先處理。

Priority Queue：

A(2)
B(5)
C(1)
D(4)

先處理 B

因為規則改成：

誰現在 priority 最高
        ↓
     誰先處理

我們沒有改變「資料」，它還是：

A
B
C
D

有異動的是之間的處理規則，而這正是資料結構真正重要的地方。

資料結構不是單純拿來裝資料的容器
它同時表達了我們認為這些資料應該如何被操作

今天真正需要記住的

Queue 表達的是先進先出(FIFO)。

Priority Queue 表達的則是優先權先決(Highest / Lowest Priority First)。
Priority Queue 常見的核心需求可以理解成：

• Repeated Maximum Selection 權重大的優先
• Repeated Minimum Selection 權重小的優先

而 Heap 之所以經常被用來實作 Priority Queue，是因為它不需要維持所有元素的完整排序，只需要有效率地維護下一個最重要的元素是誰？

但比這些名詞更重要的是今天真正想建立的觀念：

當「誰先被處理」的規則改變，適合的資料結構也會跟著改變。

下一篇：如果我要最後進來的先處理呢？

現在我們已經看過兩種處理規則。

Queue：

最早進來
   ↓
最先處理

Priority Queue：

最重要
   ↓
最先處理

但生活中還有另一種很常見的情況。
假設桌上放了一疊盤子，你剛剛把一個新的盤子放到最上面，下一次要拿盤子的時候，最自然的方式通常不是把最下面那個抽出來。

而是：

最後放上去的
      ↓
   最先拿走

也就是：

Last In, First Out。

那有沒有一種資料結構，天生就是用來描述這種問題的？

下一篇，我們來看看 Stack。